package leetcode.editor.vscdev.hot100;

public class lc33 {
    
}
class Solution {
    public int search(int[] nums, int target) {
        // 基于二分查找
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while(start <= end){
            mid = start + (end - start) / 2;
            if (nums[mid] == target){
                return mid;
            }
            // 旋转数组二分后至少有一边是有序的,基于此特性进行查找
            if (nums[start] <= nums[mid]) {
                // 此说明左部分有序
                if (nums[start] <= target && target < nums[mid]) {
                    // nums[start] < target < nums[mid]
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[end]) {
                    // nums[mid] < target < nums[end]
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }

        }
        return -1;
    }
}